#include <stdio.h>
#if 0
#include "strmatch.hpp"
#else
template <size_t MaxPattern>
class kmp_matcher
{
    typedef size_t size_type;
    const char *_pattern;
    size_type _pattern_len;
    size_type sp[MaxPattern];
public:
    kmp_matcher() : _pattern(0), _pattern_len(0) { }
    void set_pattern(const char *P)
    {
        _pattern = P;
        if (P[0] == 0) /* pattern is empty */
        {
            _pattern_len = 0;
            return;
        }

        /* Compute and store sp[k] for each 0 <= k < |P|. 
         * sp[k] = length of the longest proper prefix of P[0..k] that is
         * also a suffix of P[0..k].
         */
        size_type k;
        sp[0] = 0;
        for (k = 1; P[k]; k++)
        {
            size_type v = sp[k-1];
            while (v != 0 && P[v] != P[k])
                v = sp[v-1];
            sp[k] = (P[v] == P[k])? v + 1 : 0;
        }
        _pattern_len = k;

        /* Compute and store sp'[] from the sp[]. */
        for (k = 1; P[k]; k++)
        {
            if (P[sp[k]] == P[k+1])
                sp[k] = sp[sp[k]];
        }
    }

    size_type count_matches(const char *T) const
    {
        size_type count = 0, i = 0, j = 0;
        for (;;)
        {
            /* Find first mismatch: P[j] <> T[i]. */
            for (; T[i] && P[j] == T[i]; j++, i++);
            
            /* Increment counter if full match. */
            if (P[j] == 0)
                ++count;

            /* Finish if the text is exhausted. */
            if (T[i] == 0)
                break;

            /* Find the next character in P to match against T[i]. */
            if (j == 0)
                i++;
            else
                j = sp[j-1];
        }
        return count;
    }
};
#endif

#define MAX_P 10000
#define MAX_T 1000000

static char P[MAX_P+10]; /* pattern */
static char T[MAX_T+10]; /* text */
static kmp_matcher<MAX_P> matcher;

#if 1
int main()
{
    int num_cases;
    scanf("%d", &num_cases);
    while (num_cases--)
    {
        scanf("%s %s", P, T);
        matcher.set_pattern(P);
        printf("%d\n", matcher.count_matches(T));
    }
    return 0;
}
#else
#include <stdlib.h>
int gen_int(int minv, int maxv)
{
    int k = ((rand() << 16) ^ rand()) & 0x7fffffff;
    return minv + k % (maxv - minv + 1);
}
static kmp_matcher<MAX_P> mk;
static z_matcher<MAX_P> mz;
int main()
{
    for (int t = 0; t < 100; t++)
    {
        int text_len = gen_int(1, 1000000);
        int pattern_len = gen_int(1, 10000);
        for (int i = 0; i < text_len; i++)
            T[i] = gen_int('A', 'C');
        for (int i = 0; i < pattern_len; i++)
            P[i] = gen_int('A', 'C');
        T[text_len] = 0;
        P[pattern_len] = 0;

        mz.set_pattern(P);
        mk.set_pattern(P);
        if (mz.count_matches(T) != mk.count_matches(T))
            printf("Error!\n");
    }
    printf("End\n");
    return 0;
}
#endif
